package mht.practice.ListNode;

/**
 * Created by MHT on 2017/9/15.
 */
public class reverseListNode {

    // 翻转递归（递归）
    // 递归的精髓在于你就默认reverseListRec已经成功帮你解决了子问题了！但别去想如何解决的
    // 现在只要处理当前node和子问题之间的关系。最后就能圆满解决整个问题。
    /*
         head
            1 -> 2 -> 3 -> 4

          head
            1--------------
                                |
                   4 -> 3 -> 2                            // Node reHead = reverseListRec(head.next);
               reHead      head.next

                   4 -> 3 -> 2 -> 1                    // head.next.next = head;
               reHead

                    4 -> 3 -> 2 -> 1 -> null            // head.next = null;
               reHead
     */
    public static ListNode reverseListRec(ListNode head){
        if(head == null || head.next == null){
            return head;
        }

        ListNode reHead = reverseListRec(head.next);
        head.next.next = head;      // 把head接在reHead串的最后一个后面
        head.next = null;           // 防止循环链表
        return reHead;
    }


    // 翻转链表（遍历）
    // 从头到尾遍历原链表，每遍历一个结点，
    // 将其摘下放在新链表的最前端。
    // 注意链表为空和只有一个结点的情况。时间复杂度为O（n）
    /** 示例:
     *
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     */
    public static ListNode reverseList(ListNode head) {
        // 如果链表为空或只有一个节点，无需反转，直接返回原链表表头
        if (head == null || head.next == null) {
            return head;
        }

        ListNode reHead = null;         // 反转后新链表指针
        ListNode cur = head;

        while (cur != null) {
            ListNode preCur = cur;      // 用preCur保存住对要处理节点的引用
            cur = cur.next;             // cur更新到下一个节点
            preCur.next = reHead;       // 更新要处理节点的next引用
            reHead = preCur;            // reHead指向要处理节点的前一个节点
        }

        return reHead;
    }
}
